{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 200. 岛屿数量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入:\n",
    "\n",
    "11110\n",
    "\n",
    "11010\n",
    "\n",
    "11000\n",
    "\n",
    "00000\n",
    "\n",
    "输出: 1\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入:\n",
    "\n",
    "11000\n",
    "\n",
    "11000\n",
    "\n",
    "00100\n",
    "\n",
    "00011\n",
    "\n",
    "输出: 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def num_islands(grid):\n",
    "    if not grid or not grid[0]: return 0\n",
    "    \n",
    "    width = len(grid[0])\n",
    "    height = len(grid)\n",
    "    visited = [[0] * width for i in range(height)]\n",
    "    \n",
    "    def island_area(x, y):\n",
    "        if x < 0 or x >= width or y < 0 or y >= height: return 0\n",
    "        if visited[y][x] or not grid[y][x]: return 0\n",
    "        visited[y][x] = 1\n",
    "        return 1 + island_area(x - 1, y) + island_area(x + 1, y) + island_area(x, y - 1) + island_area(x, y + 1)\n",
    "        \n",
    "    num = 0\n",
    "    for y in range(height):\n",
    "        for x in range(width):\n",
    "            if island_area(x, y) > 0: num += 1\n",
    "    \n",
    "    return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_islands([[1,1,1,1,0],\n",
    "            [1,1,0,1,0],\n",
    "            [1,1,0,0,0],\n",
    "            [0,0,0,0,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_islands([[1,1,0,0,0],\n",
    "            [1,1,0,0,0],\n",
    "            [0,0,1,0,0],\n",
    "            [0,0,0,1,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_islands([[1,1,0,1,1],\n",
    "            [1,1,0,0,1],\n",
    "            [0,0,1,0,0],\n",
    "            [1,0,0,1,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 将遍历过的陆地标记为海水，就可以不用记录访问过的位置\n",
    "def num_islands2(grid):\n",
    "    if not grid or not grid[0]: return 0\n",
    "    \n",
    "    width = len(grid[0])\n",
    "    height = len(grid)\n",
    "    \n",
    "    def island_area(x, y):\n",
    "        if x < 0 or x >= width or y < 0 or y >= height: return 0\n",
    "        if not grid[y][x]: return 0\n",
    "        grid[y][x] = 0\n",
    "        return 1 + island_area(x - 1, y) + island_area(x + 1, y) + island_area(x, y - 1) + island_area(x, y + 1)\n",
    "        \n",
    "    num = 0\n",
    "    for y in range(height):\n",
    "        for x in range(width):\n",
    "            if island_area(x, y) > 0: num += 1\n",
    "    \n",
    "    return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_islands2([[1,1,1,1,0],\n",
    "            [1,1,0,1,0],\n",
    "            [1,1,0,0,0],\n",
    "            [0,0,0,0,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_islands2([[1,1,0,0,0],\n",
    "            [1,1,0,0,0],\n",
    "            [0,0,1,0,0],\n",
    "            [0,0,0,1,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "num_islands2([[1,1,0,1,1],\n",
    "            [1,1,0,0,1],\n",
    "            [0,0,1,0,0],\n",
    "            [1,0,0,1,1]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 407. 接雨水 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个 m x n 的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。\n",
    "\n",
    " \n",
    "\n",
    "说明:\n",
    "\n",
    "m 和 n 都是小于110的整数。每一个单位的高度都大于0 且小于 20000。\n",
    "\n",
    " \n",
    "\n",
    "示例：\n",
    "\n",
    "给出如下 3x6 的高度图:\n",
    "[\n",
    "\n",
    "  [1,4,3,1,3,2],\n",
    "  \n",
    "  [3,2,1,3,2,4],\n",
    "  \n",
    "  [2,3,3,2,3,1]\n",
    "  \n",
    "]\n",
    "\n",
    "返回 4。\n",
    "\n",
    "<img src=\"images/rainwater_empty.png\">\n",
    "\n",
    "如上图所示，这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。\n",
    "\n",
    " \n",
    "<img src=\"images/rainwater_fill.png\">\n",
    "\n",
    "\n",
    "下雨后，雨水将会被存储在这些方块中。总的接雨水量是4。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def trap_rain_water(height_map):\n",
    "    if not height_map or not height_map[0]: return 0\n",
    "    width = len(height_map[0])\n",
    "    height = len(height_map)\n",
    "    visit_map = [[0] * width for i in range(height)]\n",
    "    \n",
    "    def area_of_water(x, y):\n",
    "        if x < 0 or x >= width or y < 0 or y >= height: return float('-inf')\n",
    "        if visit_map[y][x] or height_map[y][x]: return 0\n",
    "        visit_map[y][x] = 1\n",
    "        return 1 + area_of_water(x - 1, y) + area_of_water(x + 1, y) + area_of_water(x, y - 1) + area_of_water(x, y + 1)\n",
    "    \n",
    "    num_layer = max(map(max, height_map))\n",
    "    sum_area = 0\n",
    "    for i in range(num_layer):\n",
    "        layer_area = 0\n",
    "        for y in range(height):\n",
    "            for x in range(width):\n",
    "                area = area_of_water(x, y)\n",
    "                if area > 0: layer_area += area\n",
    "        sum_area += layer_area\n",
    "        for y in range(height):\n",
    "            for x in range(width):\n",
    "                height_map[y][x] = max(0, height_map[y][x] - 1)\n",
    "                visit_map[y][x] = 0\n",
    "    \n",
    "    return sum_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "trap_rain_water([[1,4,3,1,3,2],\n",
    "                 [3,2,1,3,2,4],\n",
    "                 [2,3,3,2,3,1],\n",
    "                ])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
